from ast import List


class Solution:
    cnt = 0
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(left, right):
            if left>=right:
                return
            mid = left + (right-left)//2
            merge_sort(left, mid)
            merge_sort(mid+1, right)
            merge(left, mid, right)
        
        def merge(left, mid, right):
            tmp = []
            i = left
            j = mid+1
            while i<=mid and j<=right:
                if nums[i]<=nums[j]:
                    tmp.append(nums[i])
                    i+=1
                else:
                    tmp.append(nums[j])
                    j+=1
                    self.cnt+=mid-i+1
            
            while (i<=mid):
                tmp.append(nums[i])
                i+=1
            
            while j<=right:
                tmp.append(nums[j])
                j+=1
            
            indx = 0
            for k in range(left, right+1):
                nums[k] = tmp[indx]
                indx+=1
        merge_sort(0, len(nums)-1)
        return self.cnt